package base.sort.separate;

import base.sort.IMutableSorter;
import base.sort.Swapper;

/**
 * 快速排序，比x小 x 比x大
 */
public class QuickSortMutable implements IMutableSorter {
    @Override
    public void sort(int[] A) {
        quickSort(A, 0, A.length);
    }

    private void quickSort(int[] A, int l, int r) {
        // 递归的退出条件
        if (r-l <= 1) {
            return;
        }

        int i = partition(A, l, r);

        quickSort(A, l, i);
        quickSort(A, i+1, r);
    }

    /**
     * x｜---left---｜---mid---｜---right---|
     */
    private int partition(int[] A, int l, int r) {
        // x指向最左边
        int x = A[l];
        int i = l + 1;
        int j = r;
        while (i != j) {
            if (A[i] < x) {
                i++;
            } else {
                Swapper.swap(A, i, --j);
            }
        }
        Swapper.swap(A, i-1, l);
        return i-1;
    }
}
